package com.example.lettcode._202411._20241113;

import java.util.*;

/*
136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：
输入：nums = [2,2,1]
输出：1

示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：
输入：nums = [1]
输出：1
 */
public class _01_Zhi_chu_xian_yi_ci_de_shu_zi {

    public static void main(String[] args) {
        int[] nums = {-1, -1, -2};
        System.out.println(singleNumber3(nums));
    }

    public static int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
            if (integerIntegerEntry.getValue() == 1) {
                return integerIntegerEntry.getKey();
            }
        }

        return -1;
    }

    /*
        使用异或
        1、任何数和0进行异或，都为自身
        2、任何数和自身进行异或，都为0
        3、异或满足交换律和结合律
            a ^ b ^ c = a ^ c ^ b
            所以：数组[4,1,2,1,2]
            4 ^ 1 ^ 2 ^ 1^ 2 = 4 ^ 1 ^ 1 ^ 2 ^ 2 = 4
     */
    public static int singleNumber2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        int sigle = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sigle ^= nums[i];
        }
        return sigle;
    }

    /*
        耗时太久
     */
    public static int singleNumber3(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                list.remove(Integer.valueOf(nums[i]));
            } else {
                list.add(nums[i]);
            }
        }
        return list.get(0);
    }
}
